package leetcode.editor.day;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

// 768. 最多能完成排序的块 II
// https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/
class MaxChunksToMakeSortedIi {
    public static void main(String[] args) {
        Solution solution = new MaxChunksToMakeSortedIi().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 单调栈：https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/solution/zui-duo-neng-wan-cheng-pai-xu-de-kuai-ii-deng-jie-/
        /*public int maxChunksToSorted(int[] arr) {
            // 栈中保存了每个数组的最大值，大于等于最大值可以新分割一个数组，小于最大值可以合并前面的块
            Stack<Integer> stack = new Stack<>();
            for (int val : arr) {
                if (!stack.isEmpty() && stack.peek() > val) {
                    // 合并数组的头，最大值
                    Integer head = stack.pop();
                    // 不等于，求最大，等于可以多划分几个
                    while (!stack.isEmpty() && stack.peek() > val) stack.pop();  // 都出栈，表示合并乘一个数组
                    stack.push(head);
                } else stack.push(val);
            }

            return stack.size();
        }*/

        // 排序成另一个数组，通过hash表来表示两个数组一个区间的频率，如果hash表为空，那么表示前面的数组都是相同数字，但是无序，可以合并
        // https://leetcode.cn/problems/max-chunks-to-make-sorted-ii/solution/zui-duo-neng-wan-cheng-pai-xu-de-kuai-ii-w5c6/
        public int maxChunksToSorted(int[] arr) {
            Map<Integer, Integer> map = new HashMap<>();
            int[] sortArr = new int[arr.length];
            int count = 0;
            System.arraycopy(arr, 0, sortArr, 0, arr.length);
            Arrays.sort(sortArr);
            for (int i = 0; i < arr.length; i++) {
                int x = arr[i], y = sortArr[i];
                map.put(x, map.getOrDefault(x, 0) - 1);
                if (map.get(x) == 0) map.remove(x);

                map.put(y, map.getOrDefault(y, 0) + 1);
                if (map.get(y) == 0) map.remove(y);

                if (map.isEmpty()) count++;
            }

            return count;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
